package com.topInterview;

import jdk.nashorn.internal.ir.CallNode;

import java.util.HashMap;
import java.util.LinkedHashMap;

public class LRUCache<V> {



    public class Node<K, V> {
        private K key;
        private V value;
        private Node<K, V> last;
        private Node<K, V> next;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }

    }


    //实现一个双向链表
    public class NodeDoubleLinkedList<K, V> {
        private Node<K, V> head;
        private Node<K, V> tail;

        public NodeDoubleLinkedList() {
            head = null;
            tail = null;
        }

        public void addNode(Node<K, V> newNode) {
            if (newNode == null) {
                return;
            }
            if (head == null) {
                head = newNode;
                tail = newNode;
            } else {
                tail.next = newNode;
                newNode.last = tail;
                tail = newNode;
            }
        }

        //节点一定双向链表上
        public void moveNodeToTail(Node<K, V> node) {
            if (this.tail == node) {
                //当前节点已经是尾部了
                return;
            }
            if (this.head == node) {
                //换头
                this.head = head.next;
                //换上来的头需要把原先last指针指向空
                this.head.last = null;
            } else {
                //当前节点的上一个节点的next需要指向node的下一个节点，node.next的上一个节点需要指向node.last
                node.last.next = node.next;
                node.next.last = node.last;
            }

            node.last = tail;
            node.next = null;
            this.tail.next = node;
            this.tail = node;
        }

        public Node<K, V> removeHead() {
            if (this.head == null) {
                return null;
            }

            Node<K, V> res = this.head;
            if (this.head == this.tail) {
                //只有一个节点
                this.head = null;
                this.tail = null;
            } else {
                this.head = res.next;
                res.next = null;
                this.head.last = null;
            }
            return res;
        }
    }

    public class MyCache<K, V> {
        private HashMap<K, Node<K, V>> keyNodeMap;
        private NodeDoubleLinkedList<K, V> nodeList;
        private int capacity;

        public MyCache(int cap) throws Exception {
            if (cap < 1) {
                throw new Exception("should be more than 0");
            }
            keyNodeMap = new HashMap<>();
            nodeList = new NodeDoubleLinkedList<>();
            capacity = cap;
        }


        public V get(K key) {
            if (keyNodeMap.containsKey(key)) {
                Node<K, V> kvNode = keyNodeMap.get(key);
                nodeList.moveNodeToTail(kvNode);
                return kvNode.value;
            }
            return null;
        }


        public void set(K key, V value) {
            if (keyNodeMap.containsKey(key)) {
                //包含的情况
                Node<K, V> kvNode = keyNodeMap.get(key);
                kvNode.value = value;
                nodeList.moveNodeToTail(kvNode);
            } else {
                //新增操作
                Node node = new Node(key, value);
                keyNodeMap.put(key, node);
                nodeList.addNode(node);
                if (keyNodeMap.size() == capacity) {
                    //从链表中删除头节点，并从map中删除记录
                    Node<K, V> kvNode = nodeList.removeHead();
                    keyNodeMap.remove(kvNode.key);
                }
            }
        }
    }


}
